K-means++ is an important algorithm to choose initial cluster centers for the k-means clustering algorithm. In this work, we present a new algorithm that can solve the $k$-means++ problem with near optimal running time. Given $n$ data points in $\mathbb{R}^d$, the current state-of-the-art algorithm runs in $\widetilde{O}(k )$ iterations, and each iteration takes $\widetilde{O}(nd k)$ time. The overall running time is thus $\widetilde{O}(n d k^2)$. We propose a new algorithm \textsc{FastKmeans++} that only takes in $\widetilde{O}(nd + nk^2)$ time, in total.
translated by 谷歌翻译
从HTML文档中提取结构化信息是一个长期研究的问题，其中包括知识库构造，面积搜索和个性化建议。先前的工作依靠每个目标网站上的一些人体标记的网页或一些从某些种子网站的人类标记的网页来培训可转移的提取模型，该模型在看不见的目标网站上概括。嘈杂的内容，较低的站点级别的一致性以及缺乏通信协议使标签网页成为耗时且昂贵的磨难。我们开发的最少是半结构化Web文档的标签有效的自我训练方法，以克服这些限制。至少利用一些人标记的页面来伪造来自目标垂直行业的大量未标记的网页。它使用自我训练对人类标记和伪标记的样品进行了可转移的Web取消模型训练。为了减轻由于嘈杂的训练样本而导致的错误传播，至少根据其估计的标签准确性重新重量重量，并将其纳入培训。据我们所知，这是第一项提出端到端培训的工作，用于仅利用少数人标记的页面进行可转移的Web提取模型。大规模公共数据集的实验表明，每个种子网站上使用少于十个人体标记的页面进行培训，最不受欢迎的模型在未见网站上的平均f1点以上的最新型号超过26个平均F1点，减少人类标记的页面的数量，以达到超过10倍的性能。
translated by 谷歌翻译
在带有多个扬声器的视频中，主动扬声器检测（ASD）是一项具有挑战性的任务，因为它需要在长时间的暂时窗口上学习有效的视听功能和时空相关性。在本文中，我们提出了一种新颖的时空图形学习框架，可以解决复杂的任务，例如ASD。为此，视频框架中的每个人首先在该框架的唯一节点中编码。对应于跨帧的单个人的节点已连接以编码其时间动力学。帧中的节点也连接到编码人际关系。因此，咒语将ASD减少到节点分类任务。重要的是，咒语能够在所有节点上为所有节点上的长时间环境推理，而无需依赖计算昂贵的完全连接的图形神经网络。通过对Ava-Activespeaker数据集进行的广泛实验，我们证明了基于图形的表示形式可以显着改善主动扬声器检测性能，因为其明确的空间和时间结构。拼写优于所有先前的最新方法，同时需要大大降低内存和计算资源。我们的代码可在https://github.com/sra2/spell上公开获取
translated by 谷歌翻译
动态场景图表形式的结构化视频表示是有关多个视频理解任务的有效工具。与场景图的任务相比，由于场景的时间动态和预测的固有时间波动，动态场景图生成是更具挑战性。我们表明捕获长期依赖性是有效生成动态场景图的关键。我们通过从视频中构造一致的长期对象轨迹来介绍检测跟踪 - 识别范例，然后是捕获对象和视觉关系的动态。实验结果表明，我们的动态场景图检测变压器（DSG-DETR）在基准数据集动作基因组上的显着余量优于最先进的方法。我们还进行消融研究并验证所提出的方法的每个组成部分的有效性。
translated by 谷歌翻译
我们通过新的框架解决了主动扬声器检测问题，称为法术，从而了解远程多模式图来编码音频和视觉数据之间的模态关系。我们将主动扬声器检测作为了解长期依赖项的节点分类任务。我们首先从视频构造图形，以便每个节点对应一个人。表示在定义的时间窗口中它们之间相同身份的共享边缘的节点。同一视频帧中的节点也连接以编码人际交互。通过对AVA-ActiveSpeaker数据集的广泛实验，我们证明了基于学习的基于图形的表示，由于其明确的空间和时间结构，显着提高了整体性能。法术优于若干相关基线，并在现有技术的比例下执行，同时需要较小的计算成本阶数。
translated by 谷歌翻译
代理商通信可能会显着提高需要协调以实现共享目标的多代理任务的性能。事先工作表明，可以使用多智能体增强学习和消息传递网络架构学习代理商通信协议。然而，这些模型使用不受约束的广播通信模型，其中代理在每个步骤中与所有其他代理通信，即使任务不需要它。在现实世界应用中，如果通信可以受系统限制的限制，如带宽，电源和网络容量，则可能需要减少发送的消息的数量。在这项工作中，我们探讨了最大限度地减少通信的简单方法，同时在多任务学习中最大化性能：同时优化特定于任务的目标和通信惩罚。我们表明，目的可以使用强化和Gumbel-Softmax Reparameterization优化。我们介绍了两种稳定培训的技术：50％的培训和消息转发。在仅50％的剧集中培训沟通惩罚可防止我们的模型关闭外向消息。其次，重复消息先前接收的消息有助于模型保留信息，并进一步提高性能。通过这些技术，我们表明我们可以减少75％的通信，没有损失。
translated by 谷歌翻译